/*************************************************************************
	> File Name: 寻找中位数.cpp
	> Author: ma6174
	> Mail: ma6174@163.com 
	> Created Time: Sun 21 Apr 2013 07:40:33 PM CST
 ************************************************************************/

#include<iostream>
using namespace std;

/*
 * 有两个已排好序的数组A和B，长度均为n，找出这两个数组合并后的中间元素，要求时间代价为O(logn)。
 */

void FindMid(int A[], int B[], int N) {
	if (N == 1) {
		cout << (A[0] >= B[0] ? A[0] : B[0]) << endl;;
		return;
	}

	int mid = N / 2;

	if (A[mid] == B[mid]) {
		cout << (A[mid] >= B[mid] ? A[mid] : B[mid]) << endl;
		return;
	} else if (A[mid] < B[mid]) {
		FindMid(A + mid, B, N - mid); 
	} else {
		FindMid(A, B + mid, N - mid); 
	}
}

int main() {
	int A[] = {1, 2, 3};
	int B[] = {4, 5, 8};

	FindMid(A, B, 3);
	return 0;
}
